package ch.ams.fhnw.sudoku;




public class SudokuSolver3 {
	
	private long solveTime;
	private long iterations;
	private final int[][] data;
	private int[][] result;
	private boolean solutionFound;
	
	public SudokuSolver3(int[][] data) {
		if(data == null || data.length != 9 || data[0].length != 9) {
			throw new IllegalStateException("incorrect sudoku data format");
		}
		
		this.data = data;
		result = null;
	}
	
	public void solve() {
		long startTime = System.currentTimeMillis();
		
		solve(copyData(data), 0, 0);
		
		if (result == null) {
			solutionFound = false;
			result = copyData(data);
		} else {
			solutionFound = true;
		}
		
		solveTime = System.currentTimeMillis() - startTime;
	}
	
	public boolean validate() {
		return true;
	}
	
	private void solve(int[][] data, int row, int column) {
		if (result != null) {
			return; //result found
		}
		
		iterations++;
		int nextRow = 0;
		int nextColumn = 0;

		// index empty
		if (data[row][column] == 0) { 

			// check all possible numbers for index
			for (int possibleNumber = 1; possibleNumber < 10; possibleNumber++) {
				
				//check sudoku rules
				if (checkRow(data, column, possibleNumber) 
						&& checkColumn(data, row, possibleNumber)
						&& checkBlock(data, row, column, possibleNumber)) {
					
					data[row][column] = possibleNumber;
					
					if (row == 8 && column == 8) {
						result = data; //result found
						return;
					}

					// next iteration
					if (column == 8) {
						nextRow = row + 1;
						nextColumn = 0;
					} else {
						nextRow = row;
						nextColumn = column + 1;
					}
					solve(data, nextRow, nextColumn);
					if (result == null) {
						//no result found, reset possible number
						data[row][column] = 0; 
					}
				}
			}
			return; // no possible number found
		}
		
		if (row == 8 && column == 8) {
			result = data; // result found
			return;
		}

		//next iteration
		if (column == 8) {
			nextRow = row + 1;
			nextColumn = 0;
		} else {
			nextRow = row;
			nextColumn = column + 1;
		}
		solve(data, nextRow, nextColumn); 
	}
	
	

	private int[][] copyData(int[][] data) {
		int[][] copy = new int[9][9];
		
		for(int column = 0; column < 9; column++) {
			for (int row = 0; row < 9; row++) {
				copy[row][column] = data[row][column];
			}
		}
		
		return copy;
	}
	
	
	
	private boolean checkColumn(int[][] data, int row, int number) {
		
		for (int column = 0; column < 9 ; column++) {
			if (data[row][column] == number) {
				return false;
			}
		}
		
		return true;
	}
	
	
	
	private boolean checkRow(int[][] data, int column, int number) {
		
		for (int row = 0; row < 9 ; row++) {
			if (data[row][column] == number) {
				return false;
			}
		}
		
		return true;
	}
	
	
	
	private boolean checkBlock(int[][] data, int row, int column, int number) {
		
		int rowStart = (int) (row / 3) * 3 ;
	    int columnStart = (int) (column / 3) * 3 ;
		
	    for (int rowIdx = rowStart; rowIdx < (rowStart + 3) ; rowIdx++) {
	    	for (int columnIdx = columnStart; columnIdx < (columnStart + 3); columnIdx++) {
	    		if (data[rowIdx][columnIdx] == number) {
	    			return false;
	    		}
	    	}
	    }
	    
		return true;
	}
	
	
	public long getSolveTime() {
		return solveTime;
	}

	public long getIterations() {
		return iterations;
	}

	public int[][] getData() {
		return data;
	}
	
	public boolean hasSolution() {
		return solutionFound;
	}
	
	public int[][] getResult(){
		return result;
	}
}
